#pragma once

#include <iostream>
using namespace std;

namespace key
{
	template <class K>
	struct BSTNode
	{
		K _key;
		BSTNode<K>* _left;
		BSTNode<K>* _right;

		BSTNode(const K& key = K())
			:_key(key)
			, _left(nullptr)
			, _right(nullptr)
		{}

	};

	template <class K>
	class BSTree
	{
		typedef BSTNode<K> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}

		bool Insert(const K& key)
		{
			// 如果为空树，则直接建立一个节点
			// 将其地址存放在_root上
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;

			// 一直循环到cur为空
			while (cur) {
				if (key > cur->_key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					// 如果中途发现BS树已有key，则插入失败
					// BS树中没有重复元素，依据定义
					return false;
				}
			}

			// 此时建立一个节点，将其地址赋值给cur
			cur = new Node(key);

			// 此时需要根据值的大小来判断parent左链还是右链
			if (key > parent->_key)
				parent->_right = cur;
			else parent->_left = cur;

			return true;
		}

		bool Find(const K& key)
		{
			Node* cur = _root;

			while (cur) {
				if (key > cur->_key)
					cur = cur->_right;

				else if (key < cur->_key)
					cur = cur->_left;

				else return true;
			}

			return false;
		}

		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (key > cur->_key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					// 此时cur找到了节点
					// 该节点就是我们想要删除的节点

					// 如果左孩子为空
					// 这时候就要parent就要链到cur的右边去
					if (cur->_left == nullptr) {
						// 如果这个时候cur就是根
						// 那就_root移动一下
						if (parent == nullptr) {
							_root = _root->_right;

							delete cur;
							cur = nullptr;
							return true;
						}

						if (parent->_left == cur)
							parent->_left = cur->_right;
						else parent->_right = cur->_right;

						// 删除
						delete cur;
						cur = nullptr;

						return true;
					}

					// 如果右孩子为空
					// 这时候就要parent就要链到cur的左边去
					else if (cur->_right == nullptr) {
						// 如果这个时候cur就是根
						// 那就_root移动一下
						if (parent == nullptr) {
							_root = _root->_left;

							delete cur;
							cur = nullptr;
							return true;
						}

						if (parent->_left == cur)
							parent->_left = cur->_left;
						else parent->_right = cur->_left;

						// 删除
						delete cur;
						cur = nullptr;

						return true;
					}

					// 需要注意的是
					// 前面两种情况看似只包含了cur节点有一个孩子的情况
					// 其实也将cur节点没有孩子的情况处理了
					// 现在只要处理当cur节点有两个孩子的时候了
					// 这时候我们采用替换删除法
					// 找到右子树最小 或者 左子树最大都行
					// 因为要找的这个节点在不影响树形结构的前提下
					// 要做到大于所有cur左子树的，小于所有cur右子树的
					// 在这里，我们选择前者，即右子树最小的，也就是右子树最左侧的
					else {
						Node* rightMinP = cur;
						Node* rightMin = cur->_right;

						// 找到右子树的最小节点
						while (rightMin->_left) {
							rightMinP = rightMin;
							rightMin = rightMin->_left;
						}

						// 替代，这时候转换成就要删除rightMin这个节点了
						// 这个时候就需要有它的父亲
						cur->_key = rightMin->_key;

						// 因为rightMin必然是最左节点
						// 所以rightMinP必然是链接rightMin的右孩子
						// 同时rightMinP是左链还是右链这不确定，需要判断一下
						if (rightMinP->_left == rightMin)
							rightMinP->_left = rightMin->_right;
						else rightMinP->_right = rightMin->_right;

						delete rightMin;
						rightMin = nullptr;

						return true;
					}
				}
			}

			return false;
		}


		// 中序遍历，因为外部无妨访问私有变量_root
		// 于是封装一下
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		// 函数名前面加_表示子函数
		void _InOrder(Node* _root)
		{
			if (_root == nullptr) {
				return;
			}

			_InOrder(_root->_left);
			cout << _root->_key << " ";
			_InOrder(_root->_right);
		}
	private:
		Node* _root;
	};
}

namespace keyValue
{
	template <class K, class V>
	struct BSTNode
	{
		K _key;
		V _value;

		BSTNode<K, V>* _left;
		BSTNode<K, V>* _right;

		BSTNode(const K& key, const V& value)
			:_key(key)
			,_value(value)
			,_left(nullptr)
			,_right(nullptr)
		{}

	};

	template <class K, class V>
	class BSTree
	{
		typedef BSTNode<K, V> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}

		bool Insert(const K& key, const V& value)
		{
			// 如果为空树，则直接建立一个节点
			// 将其地址存放在_root上
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;

			// 一直循环到cur为空
			while (cur) {
				if (key > cur->_key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					// 如果中途发现BS树已有key，则插入失败
					// BS树中没有重复元素，依据定义
					return false;
				}
			}

			// 此时建立一个节点，将其地址赋值给cur
			cur = new Node(key, value);

			// 此时需要根据值的大小来判断parent左链还是右链
			if (key > parent->_key)
				parent->_right = cur;
			else parent->_left = cur;

			return true;
		}

		Node* Find(const K& key)
		{
			Node* cur = _root;

			while (cur) {
				if (key > cur->_key)
					cur = cur->_right;

				else if (key < cur->_key)
					cur = cur->_left;

				else return cur;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (key > cur->_key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					// 此时cur找到了节点
					// 该节点就是我们想要删除的节点

					// 如果左孩子为空
					// 这时候就要parent就要链到cur的右边去
					if (cur->_left == nullptr) {
						// 如果这个时候cur就是根
						// 那就_root移动一下
						if (parent == nullptr) {
							_root = _root->_right;

							delete cur;
							cur = nullptr;
							return true;
						}

						if (parent->_left == cur)
							parent->_left = cur->_right;
						else parent->_right = cur->_right;

						// 删除
						delete cur;
						cur = nullptr;

						return true;
					}

					// 如果右孩子为空
					// 这时候就要parent就要链到cur的左边去
					else if (cur->_right == nullptr) {
						// 如果这个时候cur就是根
						// 那就_root移动一下
						if (parent == nullptr) {
							_root = _root->_left;

							delete cur;
							cur = nullptr;
							return true;
						}

						if (parent->_left == cur)
							parent->_left = cur->_left;
						else parent->_right = cur->_left;

						// 删除
						delete cur;
						cur = nullptr;

						return true;
					}

					// 需要注意的是
					// 前面两种情况看似只包含了cur节点有一个孩子的情况
					// 其实也将cur节点没有孩子的情况处理了
					// 现在只要处理当cur节点有两个孩子的时候了
					// 这时候我们采用替换删除法
					// 找到右子树最小 或者 左子树最大都行
					// 因为要找的这个节点在不影响树形结构的前提下
					// 要做到大于所有cur左子树的，小于所有cur右子树的
					// 在这里，我们选择前者，即右子树最小的，也就是右子树最左侧的
					else {
						Node* rightMinP = cur;
						Node* rightMin = cur->_right;

						// 找到右子树的最小节点
						while (rightMin->_left) {
							rightMinP = rightMin;
							rightMin = rightMin->_left;
						}

						// 替代，这时候转换成就要删除rightMin这个节点了
						// 这个时候就需要有它的父亲
						cur->_key = rightMin->_key;

						// 因为rightMin必然是最左节点
						// 所以rightMinP必然是链接rightMin的右孩子
						// 同时rightMinP是左链还是右链这不确定，需要判断一下
						if (rightMinP->_left == rightMin)
							rightMinP->_left = rightMin->_right;
						else rightMinP->_right = rightMin->_right;

						delete rightMin;
						rightMin = nullptr;

						return true;
					}
				}
			}

			return false;
		}


		// 中序遍历，因为外部无妨访问私有变量_root
		// 于是封装一下
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		// 函数名前面加_表示子函数
		void _InOrder(Node* _root)
		{
			if (_root == nullptr) {
				return;
			}

			_InOrder(_root->_left);
			cout << _root->_key << ":" << _root->_value << endl;
			_InOrder(_root->_right);
		}
	private:
		Node* _root;
	};
}
